In [1]:
%%HTML
<style>
.container { width:100% }
</style>
This notebook defines the game Connect Four. You can play it online at: http://www.connectfour.org/connect-4-online.php.
Connect Four is played on a $6 \times 7$ board. Instead of Red and Yellow we call the players Xand O. Player X starts. Player X and O take turns to choose columns that are not yet filled. When player X chooses column c, the first non-empty field in column c is filled with an "X". Likewise, when player O chooses column c, the first non-empty field in column c is filled with an "X". Rows are numbered from the bottom up, i.e. the bottom row is row $0$. The goal of the game for player X is to get four consecutive Xs into a row, column, or diagonal line, while player O needs to get four consecutive Os into a row, column, or diagonal line.
In [2]:
Players = [ "X", "O" ]
States are represented as tuples of tuples. The game starts with an empty board. An empty field on the board is represented as the string ' '.
In [3]:
Start = tuple( tuple(' ' for col in range(7)) for row in range(6))
Start
Out[3]:
The function to_list transforms a tuple of tuples into a list of lists.
In [4]:
to_list = lambda State: [list(row) for row in State]
The function to_tuple transforms a list of lists into a tuple of tuples.
In [5]:
to_tuple = lambda State: tuple(tuple(row) for row in State)
The function find_empty takes two arguments:
State is a description of the board,col specifies a column, i.e. it is an integer from the set $\{0, \cdots, 6\}$.Given the State the function find_empty(State, col) returns the smallest $\texttt{row} \in \{0, \cdots, 5\}$ such that
State[row][col] == ' 'holds. If the specified column is already completely filled, then instead None is returned.
In [6]:
def find_empty(State, col):
for row in range(6):
if State[row][col] == ' ':
return row
return None
Given a State and the player who has the next move, the function next_states(State, player) computes the set of states that can be reached from State.
In [7]:
def next_states(State, player):
Empty = set()
for col in range(7):
row = find_empty(State, col)
if row != None:
Empty.add( (row, col) )
Result = set()
for (row, col) in Empty:
NextState = to_list(State)
NextState[row][col] = player
NextState = to_tuple(NextState)
Result.add(NextState)
return Result
The variable All_Lines collects the coordinates of all groups of four fields that are consecutive horizontally, vertically, or diagonally.
In [8]:
# horizontal lines
All_Lines = [ [ (row, col+x) for x in range(3+1) ] for col in range(4)
for row in range(6)
]
# vertical lines
All_Lines += [ [ (row+x, col) for x in range(4) ] for col in range(7)
for row in range(3)
]
# rising diagonals
All_Lines += [ [ (row+x, col+x) for x in range(4) ] for col in range(4)
for row in range(3)
]
# falling diagonals
All_Lines += [ [ (row+x, col-x) for x in range(4) ] for col in range(3, 7)
for row in range(3)
]
In [9]:
len(All_Lines)
Out[9]:
Given a State the function top_line_filled(State) checks whether all marks in the top line of the given board are filled.
In [10]:
def top_line_filled(State):
return ' ' not in State[5]
The function utility takes two arguments:
State is a tuple of tuple representing the board.player is a player.The function returns 1 if player has won the game, -1 if the game is lost for player, 0 if its a draw, and None if the game has not yet been decided.
In [11]:
def utility(State, player):
# all lines are checked whether they contain 4 identical nonempty marks
for Line in All_Lines:
Chars = { State[r][c] for (r, c) in Line }
if len(Chars) == 1 and Chars != { ' ' }:
if Chars == { player }:
return 1
else:
return -1
# no winner so far, check for a draw
if top_line_filled(State): # no empty squares
return 0
return None
The function heuristic tries to guess the value of a state. As it is never called in terminal states, it assumes that the game will be drawn.
In [12]:
def heuristic(State, player):
result = 0.0
# all lines are checked whether they contain 3 identical nonempty marks
for Line in All_Lines:
List = [ State[r][c] for (r,c) in Line
if State[r][c] != ' '
]
if len(List) == 3:
Chars = set(List)
if len(Chars) == 1:
if Chars == { player }:
result += 1/10
else:
result -= 1/10
if len(List) == 2:
Chars = set(List)
if len(Chars) == 1:
if Chars == { player }:
result += 1/100
else:
result -= 1/100
return result
finished(State) is True if the game is over.
In [13]:
def finished(State):
return utility(State, "X") != None
The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.
In [ ]:
def get_move(State):
State = to_list(State)
while True:
col = input("Enter column here: ")
col = int(col)
row = find_empty(State, col)
if row != None:
State[row][col] = 'O'
return to_tuple(State)
else:
print("Don't cheat. Please try again.")
This function informs the user about the result of the game once the game is finished.
In [ ]:
def final_msg(State):
if finished(State):
if utility(State, "O") == 1:
print("You have won!")
elif utility(State, "O") == -1:
print("You have lost!")
else:
print("It's a draw.");
return True
return False
In [ ]:
import ipycanvas as cnv
In [ ]:
size = 50
This function creates the canvas for the start state. It draws an empty board which is later used for the game.
In [ ]:
def create_canvas(Start):
n = len(Start)
canvas = cnv.Canvas(size=(size * 7, size * 8))
display(canvas)
return canvas
In [ ]:
import math
The function draw takes three arguments:
State is the current state of the game.canvas is a canvas used to draw the state.value is the value of the game for player X.The function draws the given State onto canvas. Below that, the value is printed.
In [ ]:
def draw(State, canvas, value):
canvas.clear()
canvas.font = '36px sans-serif'
canvas.text_align = 'center'
canvas.text_baseline = 'middle'
for row in range(6):
for col in range(7):
x = col * size
y = row * size
canvas.line_width = 3.0
canvas.stroke_rect(x, y, size, size)
symbol = State[5-row][col]
if symbol != ' ':
x += size // 2
y += size // 2
if symbol == 'X':
canvas.fill_style ='red'
else:
canvas.fill_style ='blue'
canvas.fill_arc(x, y, 0.4*size, 0, 2*math.pi)
canvas.font = '20px sans-serif'
canvas.fill_style = 'black'
for i in range(7):
x = (i + 0.5) * size
y = 6.4 * size
canvas.fill_text(str(i), x, y)
x = 3.5 * size
y = 7.4 * size
canvas.fill_text(str(value), x, y)
In [ ]: